//695 最大海岛问题
/*
给定一个二维的 0-1 矩阵，其中 0 表示海洋， 1表示陆地。单独的或相邻的陆地可以形成岛屿，每个格子只与其上下左右四个格子相邻。求最大的岛屿面积

输入输出样例
输入是一个二维数组，输出是一个整数，表示最大的岛屿面积。

Input:
[[1,0,1,1,0,1,0,1],
[1,0,1,1,0,1,1,1],
[0,0,0,0,0,0,0,1]]
Output: 6

分析：使用深度搜索，分为主函数和辅函数解决，主函数用于遍历所有搜索位置，判断是否可以开始搜索，辅函数负责深度优先的搜索。


*/
//方法一：深度搜索 使用栈
vector<int> direction{-1, 0, 1, 0, -1}; //四个方向的遍历，创造一个数组 [-1, 0, 1, 0, -1]，每相邻两位即为上下左右四个方向之一
int maxAreaOfIsland(vector<vector<int>> &grid)
{
	//m 行尺寸   n 列尺寸
	int m = grid.size(), n = m ? grid[0].size() : 0, local_area, area = 0, x, y;

	//
	for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (grid[i][j]) //grid[i][j]=1，则为陆地，开始依次搜索
			{					
				local_area = 1; //陆地
				grid[i][j] = 0; //没有使用状态记录，因此将搜索过的点记为0，避免重复。缺点是会改变原来传入的参数
				stack<pair<int, int>> island; //创建栈
				island.push({i, j});		  //入栈
				while (!island.empty())
				{
					auto [r, c] = island.top();
					island.pop(); //
					//
					for (int k = 0; k < 4; ++k)
					{
						x = r + direction[k], y = c + direction[k + 1]; 
						if (x >= 0 && x < m &&
							y >= 0 && y < n && grid[x][y] == 1)
						{
							grid[x][y] = 0;
							++local_area; //陆地+1
							island.push({x, y});
						}
					}
				}
				area = max(area, local_area);
			}
		}
	}
	return area;
}



//方法二：递归写法  主函数用于遍历所有为所位置，判断是否可以开始；辅函数用于搜索
vector<int> direction{-1, 0, 1, 0, -1};
// 主函数
int maxAreaOfIsland(vector<vector<int>> &grid)
{
	if (grid.empty() || grid[0].empty())
		return 0;
	int max_area = 0;
	for (int i = 0; i < grid.size(); ++i)
	{
		for (int j = 0; j < grid[0].size(); ++j)
		{
			if (grid[i][j] == 1)
			{
				//
				max_area = max(max_area, dfs(grid, i, j));
			}
		}
	}
	return max_area;
}
// 辅函数
int dfs(vector<vector<int>> &grid, int r, int c)
{
	//递归先判断是否符合条件
	if (grid[r][c] == 0)
		return 0;
	grid[r][c] = 0;
	int x, y, area = 1;
	for (int i = 0; i < 4; ++i)
	{
		x = r + direction[i], y = c + direction[i + 1];
		if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size())
		{
			//
			area += dfs(grid, x, y);
		}
	}
	return area;
}
